package d2;
import java.util.*;

public class Day13 {
    public static void main(String[] args) {
        int[][] a = {{1,0,1},{0,0,0},{1,0,1}};
        //maxDistance(a);
    }
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if(n==1) return n;
        int ret=0;
        int left=0,right=0;
        for(int i=0;i<nums.length-1;i++) {
            right=nums[i+1]-nums[i];
            if(right==0) continue;
            if(left *right <=0) ret++;
            left=right;
        }
        return ret+1;
    }
    public int minInsertions(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];//以i为结尾的最长子串为回文串
        for(int i=n-1;i>=0;i--) {
            for(int j=i;j<n;j++) {
                if(s.charAt(i)==s.charAt(j)) {
                    if(i==j) dp[i][j]=1;
                    else if(i+1==j) dp[i][j]=2;
                    else dp[i][j]=dp[i+1][j-1] + 2;
                }else {
                    dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return n-dp[0][n-1];
    }
    public int maxDistance(int[][] grid) {
        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,1,-1};
        int m=grid.length,n=grid[0].length;
        boolean[][] vis = new boolean[m][n];
        Queue<int[]> q = new LinkedList<>();
        int num = 0;
        //1.从1开始扩展
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if(grid[i][j]==1) {
                    q.add(new int[]{i,j});
                    vis[i][j]=true;
                    num++;
                }
        //2.扩展
        if(num==0 || num==n*m) return -1;
        int ret=0;
        while(!q.isEmpty()) {
            int sz = q.size();
            ret++;
            for(int i=sz;i>0;i--) {
                int[] t = q.poll();
                int a=t[0],b=t[1];
                for(int k=0;k<4;k++) {
                    int x=a+dx[k],y=b+dy[k];
                    if(x>=0&&x<m&&y>=0&&y<n && !vis[x][y]) {
                        q.add(new int[]{x,y});
                        vis[x][y]=true;
                    }
                }
            }
        }
        return ret-1;
    }
}
